package 中序后序还原二叉树;
import 相同的树.TreeNode;

class Solution {
    public int postindex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postindex = postorder.length-1;
        return buildTreeChild(inorder,0,inorder.length-1,postorder);
    }
    public TreeNode buildTreeChild(int[] inorder,int inbegin,int inend, int[] postorder) {
        if (inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postindex]);
        int index = findpos(inorder,inbegin,inend,postorder[postindex]);
        if (index == -1){
            return null;
        }
        postindex--;
        root.right = buildTreeChild(inorder,index+1,inend,postorder);
        root.left = buildTreeChild(inorder,inbegin,index-1,postorder);
        return root;
    }
    private int findpos(int[] inorder, int inbegin, int inend, int pos) {
        for (int i = inbegin;i <= inend;i++){
            if (inorder[i] == pos){
                return i;
            }
        }
        return -1;
    }
}